//
// Created by 123 on 2024/4/5.
//
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);

void counting_sort_ope(Arr &arr,int k) ;
void counting_sort(Arr &arr);


int main() {
    int a[10]{9, 3, 6, 7, 1, 2, 5, 4, 5, 4};
    Arr arr = initArray(a, 10);
    counting_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void counting_sort(Arr &arr) {
    counting_sort_ope(arr,10);

}
void counting_sort_ope(Arr &arr,int k) {
    int temp[arr->length];
    int count[k];
    for (int i = 0; i < k; ++i) {
        count[i]=0;
    }
    for (int i = 0; i < arr->length; ++i) {
        //记录该元素在
        count[arr->data[i]]++;//统计每个元素出现的次数
        temp[i]=arr->data[i];//给辅助数组赋值
    }
    for (int i = 1; i < k; ++i) {
        count[i]=count[i]+count[i-1];//通过动态规划思想，得到每个元素前面有几个元素的数量加上本身的数量
    }
    for (int i = 0; i < arr->length; ++i) {
        //该元素的位置是 该元素前面元素的个数-1
        arr->data[count[temp[i]]-1]=temp[i];
        count[temp[i]]--;
    }

}
Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}
void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}